package com.yaoli.ajob;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by siemens on 4/6/2017.
 */
public class _445_AddTwoNumbersII {
    public static void main(String[] args) {
        _445_AddTwoNumbersII addTwoNumbersII = new _445_AddTwoNumbersII();

        ListNode node1 = new ListNode(5);

//        ListNode node2 = new ListNode(2);
//
//        ListNode node66 = new ListNode(4);
//
//        ListNode node3 = new ListNode(3);
//
//        node1.next = node2;
//        node2.next = node66;
//        node66.next = node3;


        ListNode node5 = new ListNode(5);

//        ListNode node6 = new ListNode(6);
//
//        ListNode node7 = new ListNode(4);
//
//        node5.next = node6;
//        node6.next = node7;


        addTwoNumbersII.addTwoNumbers(node1,node5);

    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stack1 = new Stack<ListNode>();
        Stack<ListNode> stack2 = new Stack<ListNode>();

        while(l1 != null){
            stack1.push(l1);
            l1 = l1.next;
        }

        while(l2 != null){
            stack2.push(l2);
            l2 = l2.next;
        }

        boolean jin = false;
        Stack<ListNode> result = new Stack<ListNode>();
        ListNode node = null;

        while(!stack1.empty() && !stack2.empty()){
            int a = stack1.pop().val;
            int b = stack2.pop().val;

            int num;

            if(jin == true){
                num = a + b + 1;
            }else{
                num = a + b;
            }


            if(num > 9){
                jin = true;
                num = num - 10;
            }else{
                jin = false;
            }

            node = new ListNode(num);
            result.push(node);
            node = node.next;
        }

        while(!stack1.empty()){
            int num = stack1.pop().val;

            if(jin == true){
                num = num + 1;
            }

            if(num > 9){
                jin = true;
                num = num - 10;
            }else{
                jin = false;
            }

            node = new ListNode(num);
            result.push(node);
            node = node.next;
        }

        while(!stack2.empty()){
            int num = stack2.pop().val;

            if(jin == true){
                num = num + 1;
            }

            if(num > 9){
                jin = true;
                num = num - 10;
            }else{
                jin = false;
            }

            node = new ListNode(num);
            result.push(node);
            node = node.next;
        }

        if(jin == true){
            node = new ListNode(1);
            result.push(node);
            node = node.next;
        }

        ListNode node1 = null;

        List<ListNode> list = new ArrayList<ListNode>();

        while( !result.empty() ){
            int num = result.pop().val;
            node1 = new ListNode(num);
            list.add(node1);
        }

        node1 = list.get(0);

        for(int i = 1; i < list.size(); i++){
            list.get(i - 1).next = list.get(i);
        }

        return node1;
    }
}
